public class Solution1219 {

    int ans=0;
    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};

    public int getMaximumGold(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        int[][] visit=new int[m][n];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]!=0){
                    dfs(i,j,grid,visit,grid[i][j]);
                }
            }
        }
        return ans;
    }

    void dfs(int x,int y,int[][] grid,int[][] visit,int cur){
        ans=Math.max(ans,cur);
        visit[x][y]=1;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (valid(xx,yy,grid.length,grid[0].length) && visit[xx][yy]==0 && grid[xx][yy]!=0){
                dfs(xx,yy,grid,visit,cur+grid[xx][yy]);
            }
        }
        visit[x][y]=0;
    }

    boolean valid(int x,int y,int m,int n){
        return x>=0 && y>=0 && x<m && y<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1219().getMaximumGold(new int[][]{{1,0,7},{2,0,6},{3,4,5},{0,3,0},{9,0,20}}));
    }
}
